/*-------------------------------------------------------------------------
 *
 * nbtsearch.c
 *	  Postgres btrees 的搜索代码。
 *
 *
 * Portions Copyright (c) 1996-2022, PostgreSQL Global Development Group
 * Portions Copyright (c) 1994, Regents of the University of California
 *
 * IDENTIFICATION
 *	  src/backend/access/nbtree/nbtsearch.c
 *
 *-------------------------------------------------------------------------
 */

#include "postgres.h"

#include "access/nbtree.h"
#include "access/relscan.h"
#include "access/xact.h"
#include "miscadmin.h"
#include "pgstat.h"
#include "storage/predicate.h"
#include "utils/lsyscache.h"
#include "utils/rel.h"


static void fc__bt_drop_lock_and_maybe_pin(IndexScanDesc fc_scan, BTScanPos fc_sp);
static OffsetNumber fc__bt_binsrch(Relation fc_rel, BTScanInsert fc_key, Buffer fc_buf);
static int	fc__bt_binsrch_posting(BTScanInsert fc_key, Page fc_page,
								OffsetNumber fc_offnum);
static bool fc__bt_readpage(IndexScanDesc fc_scan, ScanDirection fc_dir,
						 OffsetNumber fc_offnum);
static void fc__bt_saveitem(BTScanOpaque fc_so, int fc_itemIndex,
						 OffsetNumber fc_offnum, IndexTuple fc_itup);
static int	fc__bt_setuppostingitems(BTScanOpaque fc_so, int fc_itemIndex,
								  OffsetNumber fc_offnum, ItemPointer fc_heapTid,
								  IndexTuple fc_itup);
static inline void fc__bt_savepostingitem(BTScanOpaque fc_so, int fc_itemIndex,
									   OffsetNumber fc_offnum,
									   ItemPointer fc_heapTid, int fc_tupleOffset);
static bool fc__bt_steppage(IndexScanDesc fc_scan, ScanDirection fc_dir);
static bool fc__bt_readnextpage(IndexScanDesc fc_scan, BlockNumber fc_blkno, ScanDirection fc_dir);
static bool fc__bt_parallel_readpage(IndexScanDesc fc_scan, BlockNumber fc_blkno,
								  ScanDirection fc_dir);
static Buffer fc__bt_walk_left(Relation fc_rel, Buffer fc_buf, Snapshot fc_snapshot);
static bool fc__bt_endpoint(IndexScanDesc fc_scan, ScanDirection fc_dir);
static inline void fc__bt_initialize_more_data(BTScanOpaque fc_so, ScanDirection fc_dir);


/*
 *	_bt_drop_lock_and_maybe_pin()
 *
 * 解锁缓冲区；如果安全释放引脚，也要这样做。
 * 这将防止在光标坐在页面上时，真空停滞在阻塞状态尝试读取页面。
 *
 * 请参见nbtree/README中关于确保并发TID回收安全的部分。
 */
static void fc__bt_drop_lock_and_maybe_pin(IndexScanDesc fc_scan, BTScanPos fc_sp)
{
	_bt_unlockbuf(fc_scan->indexRelation, fc_sp->buf);

	if (IsMVCCSnapshot(fc_scan->xs_snapshot) &&
		RelationNeedsWAL(fc_scan->indexRelation) &&
		!fc_scan->xs_want_itup)
	{
		ReleaseBuffer(fc_sp->buf);
		fc_sp->buf = InvalidBuffer;
	}
}

/*
 *	_bt_search() -- 在树中搜索特定的scankey，
 *		或者更准确地说，是搜索可以在其上的第一个叶子页。
 *
 * 传入的scankey是插入类型的scankey（参见nbtree/README），
 * 但可以省略索引的最右列。
 *
 * 返回值是父页面指针的堆栈（即叶子级/页没有条目）。*bufP设置为叶子页面缓冲区的地址，
 * 该缓冲区已被锁定和固定。然而，父页面上没有保持任何锁！
 *
 * 如果快照参数不为NULL，则在树的下行过程将进行“旧快照”检查。
 * 在定位插入或删除时不需要此检查，因此在这些情况下使用NULL。
 *
 * 返回的缓冲区根据访问参数被锁定。此外，
 * access = BT_WRITE将允许创建并返回一个空的根页面。
 * 当access = BT_READ时，空索引将导致*bufP被设置为InvalidBuffer。
 * 此外，在BT_WRITE模式下，在搜索过程中遇到的任何不完整拆分将会被完成。
 */
BTStack
_bt_search(Relation fc_rel, BTScanInsert fc_key, Buffer *fc_bufP, int fc_access,
		   Snapshot fc_snapshot)
{
	BTStack		fc_stack_in = NULL;
	int			fc_page_access = BT_READ;

	/* 获取根页面以开始 */
	*fc_bufP = _bt_getroot(fc_rel, fc_access);

	/* 如果索引为空且access = BT_READ，则不会创建根页面。 */
	if (!BufferIsValid(*fc_bufP))
		return (BTStack) NULL;

	/* 循环每下降一层就迭代一次 */
	for (;;)
	{
		Page		fc_page;
		BTPageOpaque fc_opaque;
		OffsetNumber fc_offnum;
		ItemId		fc_itemid;
		IndexTuple	fc_itup;
		BlockNumber fc_child;
		BTStack		fc_new_stack;

		/*
		 * 竞争 -- 我们刚刚抓取的页面自从我们在其父页面（或元页面）读取其
		 * 向下链接后可能已经拆分。如果是这样，我们可能需要向右移动到它的新兄弟页面。
		 * 请这样做。
		 *
		 * 在写入模式下，允许_bt_moveright完成沿途的任何不完整拆分。
		 * 严格来说，我们只需要在我们即将插入的叶子页面上完成不完整的拆分，
		 * 而不是在任何上层级（具有不完整拆分的内部页面在_bt_getstackbuf中也会受到处理）。
		 * 但这是完成内部页面拆分的一个好机会。
		 */
		*fc_bufP = _bt_moveright(fc_rel, fc_key, *fc_bufP, (fc_access == BT_WRITE), fc_stack_in,
							  fc_page_access, fc_snapshot);

		/* 如果这是叶子页面，我们完成了 */
		fc_page = BufferGetPage(*fc_bufP);
		fc_opaque = BTPageGetOpaque(fc_page);
		if (P_ISLEAF(fc_opaque))
			break;

		/*
		 * 在此页面上查找适当的枢轴元组。它的向下链接指向
		 * 我们即将下降到的子页面。
		 */
		fc_offnum = fc__bt_binsrch(fc_rel, fc_key, *fc_bufP);
		fc_itemid = PageGetItemId(fc_page, fc_offnum);
		fc_itup = (IndexTuple) PageGetItem(fc_page, fc_itemid);
		Assert(BTreeTupleIsPivot(fc_itup) || !fc_key->heapkeyspace);
		fc_child = BTreeTupleGetDownLink(fc_itup);

		/*
		 * 我们需要在该页面/级别的新堆栈条目中保存所选枢轴元组的位置。
		 * 如果调用者最终在下一级拆分了一个页面，通常会在此处记录的位置后立即插入一个新的枢轴元组/向下链接。
		 */
		fc_new_stack = (BTStack) palloc(sizeof(BTStackData));
		fc_new_stack->bts_blkno = BufferGetBlockNumber(*fc_bufP);
		fc_new_stack->bts_offset = fc_offnum;
		fc_new_stack->bts_parent = fc_stack_in;

		/*
		 * 页面级别1是叶子之前的最低非叶子页面级别。因此，如果
		 * 我们在级别1并要求在写入模式下锁定叶子页面，
		 * 则锁定下一个页面以写入模式，因为它必须是一个叶子。
		 */
		if (fc_opaque->btpo_level == 1 && fc_access == BT_WRITE)
			fc_page_access = BT_WRITE;

		/* 释放页面上的读取锁，然后在其子页面上获取一个锁 */
		*fc_bufP = _bt_relandgetbuf(fc_rel, *fc_bufP, fc_child, fc_page_access);

		/* 好的，准备好降级 */
		fc_stack_in = fc_new_stack;
	}

	/*
	 * 如果我们被要求以写模式锁定叶子，但未能成功，那么
	 * 重新锁定。这种情况应该只发生在根页面是叶子页面（并且
	 * 是索引中唯一的页面，除了元页面）。
	 */
	if (fc_access == BT_WRITE && fc_page_access == BT_READ)
	{
		/* 用写锁交换我们的读锁 */
		_bt_unlockbuf(fc_rel, *fc_bufP);
		_bt_lockbuf(fc_rel, *fc_bufP, BT_WRITE);

		/*
		 * 竞争 - 叶子页面可能在我们释放读锁定后
		 * 但在我们获取写锁定之前已经分裂。如果是这样，我们可能需要
		 * 向右移动到它的新兄弟页面。去做吧。
		 */
		*fc_bufP = _bt_moveright(fc_rel, fc_key, *fc_bufP, true, fc_stack_in, BT_WRITE,
							  fc_snapshot);
	}

	return fc_stack_in;
}

/*
 * _bt_moveright() - 如果需要，在b树中向右移动。
 *
 * 当我们跟随一个指针到达一个页面时，该页面可能在此期间发生了变化。
 * 如果发生这种情况，我们可以保证该页面已经“向右分裂”——也就是说，任何
 * 原本出现在页面上的数据要么在该页面上，要么严格在该页面的右侧。
 *
 * 这个例程通过检查页面上的高键条目来决定我们是否需要在树中向右移动。
 * 如果该条目严格小于扫描键，或者在
 * key.nextkey=true的情况下小于等于扫描键，那么我们跟随了错误的链接
 * 并且需要向右移动。
 *
 * 传递的插入类型扫描键可以省略索引的最右列。（见nbtree/README）
 *
 * 当key.nextkey为false（通常情况）时，我们正在寻找第一个
 * >= key的项。当key.nextkey为true时，我们正在寻找第一个
 * 严格大于key的项。
 *
 * 如果forupdate为true，我们将尝试完成我们遇到的任何不完整的分裂。
 * 这在锁定目标页面以进行插入时是必需的，因为在分裂完成之前
 * 我们不允许在页面上插入。'stack'仅在forupdate为true时使用。
 *
 * 进入时，我们已经固定了缓冲区，并根据'access'参数指定的类型持有锁。
 * 如果我们向右移动，我们将释放缓冲区和锁，并在右侧兄弟页面上获取相同的。
 * 返回值是我们停止时的缓冲区。
 *
 * 如果snapshot参数不为NULL，则在树的下降过程中将进行“旧快照”检查。
 * 在插入或删除时不需要此操作，因此在这些情况下使用NULL。
 */
Buffer _bt_moveright(Relation fc_rel,
			  BTScanInsert fc_key,
			  Buffer fc_buf,
			  bool fc_forupdate,
			  BTStack fc_stack,
			  int fc_access,
			  Snapshot fc_snapshot)
{
	Page		fc_page;
	BTPageOpaque fc_opaque;
	int32		fc_cmpval;

	/*
	 * 当nextkey = false（正常情况）：如果将我们带到
	 * 此页面的扫描键 > 页面上存储的高键，则表示页面已分裂
	 * 我们需要向右移动。（pg_upgrade的！heapkeyspace索引可能
	 * 在右侧以及左侧都有一些重复项，但这只在叶子级别处理，
	 * 在_bt_search找到初始叶子页面之后。）
	 *
	 * 当nextkey = true：如果扫描键 >= 页面的高键，则向右移动。
	 * （请注意，在此情况下，key.scantid不能被设置。）
	 *
	 * 页面甚至可能分裂多次，因此根据需要扫描。
	 *
	 * 如果我们跟随了一个链接，将我们带到一个死页面，我们也必须向右移动。
	 */
	fc_cmpval = fc_key->nextkey ? 0 : 1;

	for (;;)
	{
		fc_page = BufferGetPage(fc_buf);
		TestForOldSnapshot(fc_snapshot, fc_rel, fc_page);
		fc_opaque = BTPageGetOpaque(fc_page);

		if (P_RIGHTMOST(fc_opaque))
			break;

		/*
		 * 完成我们在过程中遇到的任何未完成的拆分。
		 */
		if (fc_forupdate && P_INCOMPLETE_SPLIT(fc_opaque))
		{
			BlockNumber fc_blkno = BufferGetBlockNumber(fc_buf);

			/* 必要时升级我们的锁 */
			if (fc_access == BT_READ)
			{
				_bt_unlockbuf(fc_rel, fc_buf);
				_bt_lockbuf(fc_rel, fc_buf, BT_WRITE);
			}

			if (P_INCOMPLETE_SPLIT(fc_opaque))
				_bt_finish_split(fc_rel, fc_buf, fc_stack);
			else
				_bt_relbuf(fc_rel, fc_buf);

			/* 以正确的模式重新获取锁，并重新检查 */
			fc_buf = _bt_getbuf(fc_rel, fc_blkno, fc_access);
			continue;
		}

		if (P_IGNORE(fc_opaque) || _bt_compare(fc_rel, fc_key, fc_page, P_HIKEY) >= fc_cmpval)
		{
			/* 向右移动一页 */
			fc_buf = _bt_relandgetbuf(fc_rel, fc_buf, fc_opaque->btpo_next, fc_access);
			continue;
		}
		else
			break;
	}

	if (P_IGNORE(fc_opaque))
		elog(ERROR, "fell off the end of index \"%s\"",
			 RelationGetRelationName(fc_rel));

	return fc_buf;
}

/*
 *	_bt_binsrch() -- 在特定页面上对键进行二分查找。
 *
 * 在叶子页面上，_bt_binsrch() 返回第一个键的 OffsetNumber >= 给定的
 * scankey，或者如果 nextkey 为真，则返回 > scankey。 (注意：这
 * 特别意味着，如果 scankey > 页面上的所有键，则返回的值可能
 * 大于页面上键的数量 1。)
 *
 * 在内部（非叶子）页面上，_bt_binsrch() 返回最后一个键的
 * OffsetNumber < 给定的 scankey，或者如果 nextkey 为真则返回
 * 最后一个键 <= 给定的 scankey。 (由于 _bt_compare 将此类页面的
 * 第一个数据键视为负无穷，因此至少会有一个键 < scankey，因此结果
 * 总是指向页面上的一个键。) 该键指示正确的下降位置，以确保我们
 * 找到所有叶子键 >= 给定的 scankey（或当 nextkey 为真时，找到
 * 叶子键 > 给定的 scankey）。
 *
 * 此过程不负责向右移动，它仅检查给定页面。
 * _bt_binsrch() 对缓冲区没有锁或引用计数的副作用。
 */
static OffsetNumber fc__bt_binsrch(Relation fc_rel,
			BTScanInsert fc_key,
			Buffer fc_buf)
{
	Page		fc_page;
	BTPageOpaque fc_opaque;
	OffsetNumber fc_low,
				fc_high;
	int32		fc_result,
				fc_cmpval;

	fc_page = BufferGetPage(fc_buf);
	fc_opaque = BTPageGetOpaque(fc_page);

	/* 在使用 scantid 的同时请求 nextkey 语义似乎是毫无意义的 */
	Assert(!fc_key->nextkey || fc_key->scantid == NULL);
	/* 设置 scantid 的调用者必须在叶子页面上使用 _bt_binsrch_insert() */
	Assert(!P_ISLEAF(fc_opaque) || fc_key->scantid == NULL);

	fc_low = P_FIRSTDATAKEY(fc_opaque);
	fc_high = PageGetMaxOffsetNumber(fc_page);

	/*
	 * 如果页面上没有键，则返回第一个可用槽。注意这涵盖了两个
	 * 情况：页面确实是空的（没有键），或者它只包含一个高键。
	 * 后一种情况在清理后是可能的。然而，在内部页面上永远不会发生
	 * 这种情况，因为它们永远不会是空的（内部页面必须有子节点）。
	 */
	if (unlikely(fc_high < fc_low))
		return fc_low;

	/*
	 * 二分查找以找到页面上第一个键 >= 扫描键，或当 nextkey 为
	 * 真时第一个键 > scankey。
	 *
	 * 对于 nextkey=false (cmpval=1)，循环不变式是：'low' 之前的所有
	 * 槽 < 扫描键，'high' 及其之后的所有槽 >= 扫描键。
	 *
	 * 对于 nextkey=true (cmpval=0)，循环不变式是：'low' 之前的所有
	 * 槽 <= 扫描键，'high' 及其之后的所有槽 > 扫描键。
	 *
	 * 当高==低时，我们可以跳出循环。
	 */
	fc_high++;						/* 为高建立循环不变式 */

	fc_cmpval = fc_key->nextkey ? 0 : 1;	/* 选择比较值 */

	while (fc_high > fc_low)
	{
		OffsetNumber fc_mid = fc_low + ((fc_high - fc_low) / 2);

		/* 我们有 low <= mid < high，因此 mid 指向一个真实的槽 */

		fc_result = _bt_compare(fc_rel, fc_key, fc_page, fc_mid);

		if (fc_result >= fc_cmpval)
			fc_low = fc_mid + 1;
		else
			fc_high = fc_mid;
	}

	/*
	 * 此时我们有高==低，但要小心：它们可能指向页面上的最后一个
	 * 槽之后。
	 *
	 * 在叶子页面上，我们总是返回第一个键 >= 扫描键（响应地 >
	 * 扫描键），这可能是最后一个槽 + 1。
	 */
	if (P_ISLEAF(fc_opaque))
		return fc_low;

	/*
	 * 在非叶子页面上，返回最后一个键 < 扫描键（响应地 <= 扫描键）。
	 * 如果 _bt_compare() 遵循规则，则必须至少有一个。
	 */
	Assert(fc_low > P_FIRSTDATAKEY(fc_opaque));

	return OffsetNumberPrev(fc_low);
}

/*
 *
 *	_bt_binsrch_insert() -- 可缓存的增量叶页二分搜索。
 *
 * 类似于 _bt_binsrch()，但支持缓存二分搜索的边界。仅在插入期间使用，并且仅在看起来调用者将插入元组的叶页上使用。独占锁定并固定的叶页包含在 insertstate 中。
 *
 * 在 insertstate 中缓存边界字段，以便后续调用可以重用原始二分搜索的低和严格高边界。直接使用这些字段的调用者必须准备好处理低和/或严格高不在同一页的情况（其中一个或两个超过了页面的 maxoff）。在页面上没有项的情况（高 < 低）会使边界无效。
 *
 * 调用者在第二次调用此处之前修改页面时负责使边界失效，并处理匹配的发布列表元组（调用者可以使用 insertstate 的 postingoff 字段来确定哪个现有的堆 TID 需要通过发布列表拆分来替换）。
 */
OffsetNumber _bt_binsrch_insert(Relation fc_rel, BTInsertState fc_insertstate)
{
	BTScanInsert fc_key = fc_insertstate->itup_key;
	Page		fc_page;
	BTPageOpaque fc_opaque;
	OffsetNumber fc_low,
				fc_high,
				fc_stricthigh;
	int32		fc_result,
				fc_cmpval;

	fc_page = BufferGetPage(fc_insertstate->buf);
	fc_opaque = BTPageGetOpaque(fc_page);

	Assert(P_ISLEAF(fc_opaque));
	Assert(!fc_key->nextkey);
	Assert(fc_insertstate->postingoff == 0);

	if (!fc_insertstate->bounds_valid)
	{
		/* 开始新的二分搜索 */
		fc_low = P_FIRSTDATAKEY(fc_opaque);
		fc_high = PageGetMaxOffsetNumber(fc_page);
	}
	else
	{
		/* 恢复针对同一页面的先前二分搜索的结果 */
		fc_low = fc_insertstate->low;
		fc_high = fc_insertstate->stricthigh;
	}

	/* 如果页面上没有键，则返回第一个可用的槽 */
	if (unlikely(fc_high < fc_low))
	{
		/* 调用者无法重用边界 */
		fc_insertstate->low = InvalidOffsetNumber;
		fc_insertstate->stricthigh = InvalidOffsetNumber;
		fc_insertstate->bounds_valid = false;
		return fc_low;
	}

	/*
	 * 二分搜索以找到页面上第一个大于或等于扫描键的键。（插入时 nextkey 总是为假）。
	 *
	 * 循环不变式是：'low'之前的所有槽 < 扫描键，'high'所在或之后的所有槽 >= 扫描键。'stricthigh' > 扫描键，并被维护以节省调用者的额外搜索工作。
	 *
	 * 当高 == 低时，我们可以退出。
	 */
	if (!fc_insertstate->bounds_valid)
		fc_high++;					/* 为高建立循环不变式 */
	fc_stricthigh = fc_high;			/* 高初始值严格高于 */

	fc_cmpval = 1;					/* !nextkey 比较值 */

	while (fc_high > fc_low)
	{
		OffsetNumber fc_mid = fc_low + ((fc_high - fc_low) / 2);

		/* 我们有 low <= mid < high，因此 mid 指向一个真实的槽 */

		fc_result = _bt_compare(fc_rel, fc_key, fc_page, fc_mid);

		if (fc_result >= fc_cmpval)
			fc_low = fc_mid + 1;
		else
		{
			fc_high = fc_mid;
			if (fc_result != 0)
				fc_stricthigh = fc_high;
		}

		/*
		 * 如果二分搜索定位的偏移处的元组是与调用者的 scantid 重叠的发布列表，则执行发布列表的二分搜索以设置调用者的 postingoff。调用者必须在设置 postingoff 时拆分发布列表。这应该很少发生。
		 */
		if (unlikely(fc_result == 0 && fc_key->scantid != NULL))
		{
			/*
			 * 每个叶页二分搜索中 postingoff 不应被设置超过一次。这将意味着索引中存在重复的表 TID，这是绝对不允许的。在这里进行检查。
			 */
			if (fc_insertstate->postingoff != 0)
				ereport(ERROR,
						(errcode(ERRCODE_INDEX_CORRUPTED),
						 errmsg_internal("table tid from new index tuple (%u,%u) cannot find insert offset between offsets %u and %u of block %u in index \"%s\"",
										 ItemPointerGetBlockNumber(fc_key->scantid),
										 ItemPointerGetOffsetNumber(fc_key->scantid),
										 fc_low, fc_stricthigh,
										 BufferGetBlockNumber(fc_insertstate->buf),
										 RelationGetRelationName(fc_rel))));

			fc_insertstate->postingoff = fc__bt_binsrch_posting(fc_key, fc_page, fc_mid);
		}
	}

	/*
	 * 在叶页上，二分搜索始终返回第一个 >= 扫描键的键（至少在 !nextkey 的情况下），这可以是最后一个槽 + 1。这也是缓存搜索的下界。
	 *
	 * stricthigh 也可能是最后一个槽 + 1，这阻止调用者直接使用边界，但如果我们在第二次调用时传入缓存的边界，这仍然对我们有用（缓存的低值将 < stricthigh，当这种情况发生时）。
	 */
	fc_insertstate->low = fc_low;
	fc_insertstate->stricthigh = fc_stricthigh;
	fc_insertstate->bounds_valid = true;

	return fc_low;
}

/*----------
 *	_bt_binsrch_posting() -- 帖子列表二进制搜索。
 *
 * _bt_binsrch_insert() 的辅助例程。
 *
 * 返回调用者的 scantid 属于的帖子列表的偏移量。
 *----------
 */
static int fc__bt_binsrch_posting(BTScanInsert fc_key, Page fc_page, OffsetNumber fc_offnum)
{
	IndexTuple	fc_itup;
	ItemId		fc_itemid;
	int			fc_low,
				fc_high,
				fc_mid,
				fc_res;

	/*
	 * 如果这不是一个帖子元组，那么索引必须是损坏的（如果它是
	 * 一个普通的非支点元组，则必须存在一个具有等于插入者的新堆 TID/scantid 的堆 TID 的元组）。要防御性地
	 * 检查元组是否为帖子列表元组，其帖子列表范围是否包含调用者的 scantid。
	 *
	 * （这也是需要的，因为 contrib/amcheck 的 rootdescend 选项需要
	 * 能够使用 _bt_binsrch_insert() 重新定位一个非支点元组。）
	 */
	fc_itemid = PageGetItemId(fc_page, fc_offnum);
	fc_itup = (IndexTuple) PageGetItem(fc_page, fc_itemid);
	if (!BTreeTupleIsPosting(fc_itup))
		return 0;

	Assert(fc_key->heapkeyspace && fc_key->allequalimage);

	/*
	 * 如果帖子列表元组设置了 LP_DEAD 位，向 _bt_binsrch_insert() 调用者指示
	 * 这一点，返回 -1，这是一个哨兵值。当调用者移除死项目后，可以进行
	 * 对 _bt_binsrch_insert() 的第二次调用。
	 */
	if (ItemIdIsDead(fc_itemid))
		return -1;

	/* "high" 超过了循环不变式的帖子列表末尾 */
	fc_low = 0;
	fc_high = BTreeTupleGetNPosting(fc_itup);
	Assert(fc_high >= 2);

	while (fc_high > fc_low)
	{
		fc_mid = fc_low + ((fc_high - fc_low) / 2);
		fc_res = ItemPointerCompare(fc_key->scantid,
								 BTreeTupleGetPostingN(fc_itup, fc_mid));

		if (fc_res > 0)
			fc_low = fc_mid + 1;
		else if (fc_res < 0)
			fc_high = fc_mid;
		else
			return fc_mid;
	}

	/* 没有找到完全匹配的项 */
	return fc_low;
}

/*----------
 *	_bt_compare() -- 将插入类型的 scankey 与页面上的元组进行比较。
 *
 *	page/offnum: 要与之比较的 btree 项的位置。
 *
 *		此例程返回：
 *			<0 如果 scankey < offnum 的元组；
 *			 0 如果 scankey == offnum 的元组；
 *			>0 如果 scankey > offnum 的元组。
 *
 * 键中的 NULL 被视为可排序值。因此
 * “相等”并不一定意味着该项应作为匹配键返回给调用者。
 * 同样，设置了 scantid 的插入 scankey 会被视为与其 TID
 * 范围与其 scantid 重叠的帖子元组相等。通常在帖子元组中不会有
 * 匹配的 TID，调用者必须自己处理（例如，通过拆分帖子列表元组）。
 *
 * 关键注意事项：在非叶页面上，假定第一个数据键为
 * “负无穷”：此例程将始终声称它小于
 * scankey。实际存储的键值被明确截断为 0
 * 属性（明确的负无穷）与版本 3+ 索引，但
 * 这并不依赖于此。这使我们能够实现 Lehman 和
 * Yao 的约定，即第一个下链指针位于第一个
 * 键之前。有关详细信息，请参见 backend/access/nbtree/README。
 *----------
 */
int32 _bt_compare(Relation fc_rel,
			BTScanInsert fc_key,
			Page fc_page,
			OffsetNumber fc_offnum)
{
	TupleDesc	fc_itupdesc = RelationGetDescr(fc_rel);
	BTPageOpaque fc_opaque = BTPageGetOpaque(fc_page);
	IndexTuple	fc_itup;
	ItemPointer fc_heapTid;
	ScanKey		fc_scankey;
	int			fc_ncmpkey;
	int			fc_ntupatts;
	int32		fc_result;

	Assert(_bt_check_natts(fc_rel, fc_key->heapkeyspace, fc_page, fc_offnum));
	Assert(fc_key->keysz <= IndexRelationGetNumberOfKeyAttributes(fc_rel));
	Assert(fc_key->heapkeyspace || fc_key->scantid == NULL);

	/*
	 * 如果目标项是内部页面上的第一个数据项，则强制结果为 “>” 
	 * --- 见上面的说明。
	 */
	if (!P_ISLEAF(fc_opaque) && fc_offnum == P_FIRSTDATAKEY(fc_opaque))
		return 1;

	fc_itup = (IndexTuple) PageGetItem(fc_page, PageGetItemId(fc_page, fc_offnum));
	fc_ntupatts = BTreeTupleGetNAtts(fc_itup, fc_rel);

	/*
	 * 扫描键通过与每个键中的术语关联的属性编号进行设置。重要的是，如果
	 * 索引是多键的，则扫描应包含前 k 个键属性，并且它们应该按顺序排列。
	 * 如果你考虑多键排序的工作原理，你就会理解为什么这是。
	 *
	 * 然而，我们在这里不测试是否违反了此条件。索引扫描的初始设置最好是
	 * 正确的（见 _bt_first）。
	 */

	fc_ncmpkey = Min(fc_ntupatts, fc_key->keysz);
	Assert(fc_key->heapkeyspace || fc_ncmpkey == fc_key->keysz);
	Assert(!BTreeTupleIsPosting(fc_itup) || fc_key->allequalimage);
	fc_scankey = fc_key->scankeys;
	for (int fc_i = 1; fc_i <= fc_ncmpkey; fc_i++)
	{
		Datum		fc_datum;
		bool		fc_isNull;

		fc_datum = index_getattr(fc_itup, fc_scankey->sk_attno, fc_itupdesc, &fc_isNull);

		if (fc_scankey->sk_flags & SK_ISNULL)	/* 键为 NULL */
		{
			if (fc_isNull)
				fc_result = 0;		/* NULL "=" NULL */
			else if (fc_scankey->sk_flags & SK_BT_NULLS_FIRST)
				fc_result = -1;	/* NULL "<" NOT_NULL */
			else
				fc_result = 1;		/* NULL ">" NOT_NULL */
		}
		else if (fc_isNull)		/* 键是 NOT_NULL 而项是 NULL */
		{
			if (fc_scankey->sk_flags & SK_BT_NULLS_FIRST)
				fc_result = 1;		/* NOT_NULL ">" NULL */
			else
				fc_result = -1;	/* NOT_NULL "<" NULL */
		}
		else
		{
			/*
			 * sk_func 需要将索引值作为左参数传递，将 sk_argument 作为右参数传递（它们的类型可能不同）。
			 * 由于对调用者来说，将 _bt_compare 看作是将 scankey 与索引项进行比较是方便的，
			 * 所以我们必须翻转比较结果的符号。（除非它是一个 DESC 列，在这种情况下我们 *不* 翻转符号。）
			 */
			fc_result = DatumGetInt32(FunctionCall2Coll(&fc_scankey->sk_func,
													 fc_scankey->sk_collation,
													 fc_datum,
													 fc_scankey->sk_argument));

			if (!(fc_scankey->sk_flags & SK_BT_DESC))
				INVERT_COMPARE_RESULT(fc_result);
		}

		/* 如果键不相等，返回差值 */
		if (fc_result != 0)
			return fc_result;

		fc_scankey++;
	}

	/*
	 * 所有非截断属性（堆 TID 除外）均被发现相等。
	 * 当 scankey 具有一个否则会被直接比较的键属性值时，将截断属性视为负无穷。
	 *
	 * 注意：ntupatts 包含非键属性是无关紧要的；
	 * scankey 不会，因此显式排除非键属性不是必要的。
	 */
	if (fc_key->keysz > fc_ntupatts)
		return 1;

	/*
	 * 使用堆 TID 属性和 scantid 尝试打破平局。
	 * 规则与任何其他键属性相同 —— 只有表示形式不同。
	 */
	fc_heapTid = BTreeTupleGetHeapTID(fc_itup);
	if (fc_key->scantid == NULL)
	{
		/*
		 * 绝大多数搜索的 scankey 被认为大于一个截断的主轴元组
		 * 当且仅当该 scankey 对于直到并包括元组中的最不重要的非截断属性的属性值相等时。
		 *
		 * 例如，如果一个索引有最小的两个属性（单用户键属性，加上堆 TID 属性），
		 * 而页面的高键是（'foo', -inf），而 scankey 是（'foo', <省略>），
		 * 则搜索不会向左下降到该页面。搜索将下降到右侧。
		 * 主轴元组中的截断属性意味着在左侧页面上的所有非主轴元组严格 < 'foo'，
		 * 所以没有必要向左下降。换句话说，搜索不必向左下降，因为它对一个堆 TID 值为 -inf 的匹配不感兴趣。
		 *
		 * 然而，一些搜索（pivotsearch 搜索）实际上要求我们在这种情况下向左下降。
		 * -inf 被视为省略的 scankey 属性的可能匹配。
		 * 这是页面删除所需的，页面删除必须使用它们的高键重新查找作为删除目标的叶页面。
		 *
		 * 注意：测试的堆 TID 部分确保 scankey 正在与一个或多个截断键属性的主轴元组进行比较。
		 *
		 * 注意：pg_upgrade 的 !heapkeyspace 索引必须始终在此下降到左侧，因为它们没有堆 TID 属性（并且在任何情况下都不能有 -inf 键值，
		 * 因为截断只能移除非键属性）。!heapkeyspace 搜索必须始终准备在达到叶子级别后处理主轴两侧的匹配。
		 */
		if (fc_key->heapkeyspace && !fc_key->pivotsearch &&
			fc_key->keysz == fc_ntupatts && fc_heapTid == NULL)
			return 1;

		/* 所有提供的 scankey 参数都被发现相等 */
		return 0;
	}

	/*
	 * 将截断的堆 TID 视为负无穷，因为 scankey 有一个键属性值
	 * (scantid)，否则将直接进行比较
	 */
	Assert(fc_key->keysz == IndexRelationGetNumberOfKeyAttributes(fc_rel));
	if (fc_heapTid == NULL)
		return 1;

	/*
	 * 如果 scankey 的 scantid 值在发布列表的范围内，则必须将
	 * scankey 视为与发布列表元组相等。在所有其他情况下
	 * 只能有一个堆 TID 值，该值与 scantid 直接比较。
	 */
	Assert(fc_ntupatts >= IndexRelationGetNumberOfKeyAttributes(fc_rel));
	fc_result = ItemPointerCompare(fc_key->scantid, fc_heapTid);
	if (fc_result <= 0 || !BTreeTupleIsPosting(fc_itup))
		return fc_result;
	else
	{
		fc_result = ItemPointerCompare(fc_key->scantid,
									BTreeTupleGetMaxHeapTID(fc_itup));
		if (fc_result > 0)
			return 1;
	}

	return 0;
}

/*
 *	_bt_first() -- 在扫描中查找第一个项。
 *
 *		我们需要聪明地处理扫描方向、搜索条件和树排序。
 *		我们在树中找到第一个项（或者，如果是反向扫描，则是最后一个项），
 *		以满足扫描键的资格。在成功退出时，包含当前索引元组的页面已被固定但
 *		未被锁定，关于页面上匹配元组的数据已加载到 so->currPos 中。
 *		scan->xs_ctup.t_self 被设置为当前元组的堆 TID，
 *		如果请求，scan->xs_itup 指向索引元组的副本。
 *
 * 如果索引中没有匹配的项，我们返回 false，不持有任何
 * 固定或锁定。
 *
 * 请注意，scan->keyData[] 和由此构建的 so->keyData[] scankey 
 * 都是搜索类型的 scankeys（有关更多信息，请参见 nbtree/README）。
 * 在此例程中，我们构建一个临时的插入类型 scankey 以用于
 * 定位扫描起始位置。
 */
bool _bt_first(IndexScanDesc fc_scan, ScanDirection fc_dir)
{
	Relation	fc_rel = fc_scan->indexRelation;
	BTScanOpaque fc_so = (BTScanOpaque) fc_scan->opaque;
	Buffer		fc_buf;
	BTStack		fc_stack;
	OffsetNumber fc_offnum;
	StrategyNumber fc_strat;
	bool		fc_nextkey;
	bool		fc_goback;
	BTScanInsertData fc_inskey;
	ScanKey		fc_startKeys[INDEX_MAX_KEYS];
	ScanKeyData fc_notnullkeys[INDEX_MAX_KEYS];
	int			fc_keysCount = 0;
	int			fc_i;
	bool		fc_status;
	StrategyNumber fc_strat_total;
	BTScanPosItem *fc_currItem;
	BlockNumber fc_blkno;

	Assert(!BTScanPosIsValid(fc_so->currPos));

	pgstat_count_index_scan(fc_rel);

	/*
	 * 检查扫描键并消除任何冗余键；还标记必须匹配的
	 * 键以继续扫描。
	 */
	_bt_preprocess_keys(fc_scan);

	/*
	 * 如果 _bt_preprocess_keys() 发现扫描键永远无法满足
	 * （例如，x == 1 且 x > 2），请立即退出。
	 */
	if (!fc_so->qual_ok)
	{
		/* 通知其他任何工作者我们已完成此扫描键。 */
		_bt_parallel_done(fc_scan);
		return false;
	}

	/*
	 * 对于并行扫描，从共享状态获取起始页面。如果扫描
	 * 尚未开始，请继续以通常的方式查找第一个叶子页面，
	 * 同时让其他参与进程等待。如果扫描已经开始，请使用
	 * 共享结构中的页面编号。
	 */
	if (fc_scan->parallel_scan != NULL)
	{
		fc_status = _bt_parallel_seize(fc_scan, &fc_blkno);
		if (!fc_status)
			return false;
		else if (fc_blkno == P_NONE)
		{
			_bt_parallel_done(fc_scan);
			return false;
		}
		else if (fc_blkno != InvalidBlockNumber)
		{
			if (!fc__bt_parallel_readpage(fc_scan, fc_blkno, fc_dir))
				return false;
			goto readcomplete;
		}
	}

	/*----------
	 * 检查扫描键以发现我们需要开始扫描的位置。
	 *
	 * 我们想确定可以用作起始边界的键；这些是向前扫描的=、>或>=键，或向后扫描的=、<、<=键。只要前面的属性只有=、>=（分别是=、<=）键，我们就可以使用多个属性的键。一旦我们接受了>或<边界，或者发现一个没有边界的属性（可以认为与"> -infinity"是一样的），我们就无法对其右侧的任何属性使用键，因为这会打破我们对初始定位策略的简单概念的理解。
	 *
	 * 当扫描键包含交叉类型运算符时，_bt_preprocess_keys可能无法消除冗余键；在这种情况下，我们将为每个属性任意选择一个可用的键。这是正确的，但可能不是最佳的行为。（例如，对于键“x >= 4 AND x >= 5”，我们会选择从x=4开始扫描，而x=5会更高效。）由于这种情况只会在查询措辞不当加上不完整的opfamily时发生，因此就这样接受吧。
	 *
	 * 当单个属性出现等号和不等号键时（再次，仅在出现交叉类型运算符时才可能），我们*必须*选择其中一个等号键作为起始点，因为_bt_checkkeys()将在等号条件失败时停止扫描。例如，如果我们有键“x >= 4 AND x = 10”，并且我们选择从x=4开始，我们会失败，并在到达x=10之前停止。然而，如果多个等号条件在预处理后依然存在，使用哪个都无所谓——根据定义，它们要么是冗余的，要么是矛盾的。
	 *
	 * 任何常规键（不是SK_SEARCHNULL）都暗示着一个NOT NULL限定符。如果索引在我们将要开始的地方存储了null，并且我们在该列没有边界键（这意味着我们推断出NOT NULL的键是不等式键，约束了索引的另一端），那么我们会生成一个明确的SK_SEARCHNOTNULL键作为边界键使用。如果我们不这样做，可能会发现自己在扫描开始时遍历大量的null条目。
	 *
	 * 在这个循环中，行比较键与它们的第一个（最左侧）列的键处理方式相同。如果可能的话，我们将在下面添加行比较的低阶列。
	 *
	 * 选择的扫描键（每个索引列最多一个）通过将它们的地址存储到本地的startKeys[]数组中来记住。
	 *----------
	 */
	fc_strat_total = BTEqualStrategyNumber;
	if (fc_so->numberOfKeys > 0)
	{
		AttrNumber	fc_curattr;
		ScanKey		fc_chosen;
		ScanKey		fc_impliesNN;
		ScanKey		fc_cur;

		/*
		 * chosen是当前属性迄今为止选择的键（如果有的话）。
		 * 在我们到达下一个属性的键之前，我们不会把这个决定定下来。
		 */
		fc_curattr = 1;
		fc_chosen = NULL;
		/* 还要记住任何暗示NOT NULL约束的扫描键 */
		fc_impliesNN = NULL;

		/*
		 * 循环从0迭代到numberOfKeys（包括）；我们使用最后一次
		 * 遍历来处理最后一个键后的处理。实际退出循环
		 * 是在下面的某个“break”语句处。
		 */
		for (fc_cur = fc_so->keyData, fc_i = 0;; fc_cur++, fc_i++)
		{
			if (fc_i >= fc_so->numberOfKeys || fc_cur->sk_attno != fc_curattr)
			{
				/*
				 * 已经完成了对curattr的键的检查。如果我们没有找到
				 * 可用的边界键，看看我们是否可以推导出一个NOT NULL键。
				 */
				if (fc_chosen == NULL && fc_impliesNN != NULL &&
					((fc_impliesNN->sk_flags & SK_BT_NULLS_FIRST) ?
					 ScanDirectionIsForward(fc_dir) :
					 ScanDirectionIsBackward(fc_dir)))
				{
					/* 是的，所以在notnullkeys[keysCount]中构建键 */
					fc_chosen = &fc_notnullkeys[fc_keysCount];
					ScanKeyEntryInitialize(fc_chosen,
										   (SK_SEARCHNOTNULL | SK_ISNULL |
											(fc_impliesNN->sk_flags &
											 (SK_BT_DESC | SK_BT_NULLS_FIRST))),
										   fc_curattr,
										   ((fc_impliesNN->sk_flags & SK_BT_NULLS_FIRST) ?
											BTGreaterStrategyNumber :
											BTLessStrategyNumber),
										   InvalidOid,
										   InvalidOid,
										   InvalidOid,
										   (Datum) 0);
				}

				/*
				 * 如果我们仍然没有找到可用的边界键，退出；否则
				 * 将边界键指针保存在startKeys中。
				 */
				if (fc_chosen == NULL)
					break;
				fc_startKeys[fc_keysCount++] = fc_chosen;

				/*
				 * 调整strat_total，如果我们存储了>或<
				 * 键，则退出。
				 */
				fc_strat = fc_chosen->sk_strategy;
				if (fc_strat != BTEqualStrategyNumber)
				{
					fc_strat_total = fc_strat;
					if (fc_strat == BTGreaterStrategyNumber ||
						fc_strat == BTLessStrategyNumber)
						break;
				}

				/*
				 * 如果这是最后一个属性，或者下一个键不在
				 * 顺序中（意味着下一个属性没有可用的边界键），则完成。
				 */
				if (fc_i >= fc_so->numberOfKeys ||
					fc_cur->sk_attno != fc_curattr + 1)
					break;

				/*
				 * 为下一个属性重置。
				 */
				fc_curattr = fc_cur->sk_attno;
				fc_chosen = NULL;
				fc_impliesNN = NULL;
			}

			/*
			 * 我们可以将这个键用作该属性的起始边界吗？
			 *
			 * 如果不可以，这是否意味着存在NOT NULL约束？（因为
			 * SK_SEARCHNULL键总是分配给BTEqualStrategyNumber，
			 * *任何*不等键都适用于此；我们无需测试。）
			 */
			switch (fc_cur->sk_strategy)
			{
				case BTLessStrategyNumber:
				case BTLessEqualStrategyNumber:
					if (fc_chosen == NULL)
					{
						if (ScanDirectionIsBackward(fc_dir))
							fc_chosen = fc_cur;
						else
							fc_impliesNN = fc_cur;
					}
					break;
				case BTEqualStrategyNumber:
					/* 重写任何非等式选择 */
					fc_chosen = fc_cur;
					break;
				case BTGreaterEqualStrategyNumber:
				case BTGreaterStrategyNumber:
					if (fc_chosen == NULL)
					{
						if (ScanDirectionIsForward(fc_dir))
							fc_chosen = fc_cur;
						else
							fc_impliesNN = fc_cur;
					}
					break;
			}
		}
	}

	/*
	 * 如果我们没有找到可用的边界键，我们必须从树的一端开始。
	 * 沿着那条边走到第一个或最后一个键，然后从
	 * 那里扫描。
	 */
	if (fc_keysCount == 0)
	{
		bool		fc_match;

		fc_match = fc__bt_endpoint(fc_scan, fc_dir);

		if (!fc_match)
		{
			/* 不匹配，因此标记（并行）扫描完成 */
			_bt_parallel_done(fc_scan);
		}

		return fc_match;
	}

	/*
	 * 我们希望在索引内的某个地方开始扫描。设置一个
	 * 可以用来搜索我们上面确定的边界点的插入scankey。
	 * 插入scankey是使用startKeys[]中识别的键构建的。
	 * （剩余的插入scankey字段将在初始定位策略确定后初始化。）
	 */
	Assert(fc_keysCount <= INDEX_MAX_KEYS);
	for (fc_i = 0; fc_i < fc_keysCount; fc_i++)
	{
		ScanKey		fc_cur = fc_startKeys[fc_i];

		Assert(fc_cur->sk_attno == fc_i + 1);

		if (fc_cur->sk_flags & SK_ROW_HEADER)
		{
			/*
			 * 行比较头部：看第一行成员。
			 *
			 * 成员scankeys已经采用插入格式（即，它们
			 * 具有sk_func = 3路比较函数），但我们必须注意
			 * 空值，_bt_preprocess_keys并未检查。第一个行成员中的空值
			 * 使得条件不可匹配，就像qual_ok = false一样。
			 */
			ScanKey		fc_subkey = (ScanKey) DatumGetPointer(fc_cur->sk_argument);

			Assert(fc_subkey->sk_flags & SK_ROW_MEMBER);
			if (fc_subkey->sk_flags & SK_ISNULL)
			{
				_bt_parallel_done(fc_scan);
				return false;
			}
			memcpy(fc_inskey.scankeys + fc_i, fc_subkey, sizeof(ScanKeyData));

			/*
			 * 如果行比较是我们接受的最后一个定位键，
			 * 尝试从低阶行成员中添加附加键。
			 * （如果我们接受了对附加索引
			 * 列的独立条件，我们就使用这些条件——
			 * 并不值得尝试确定哪一个更具限制性。）请注意，即使行比较
			 * 是“>”或“<”类型，这也是可以的，因为适用于所有但最后一个
			 * 行成员的条件实际上是“>=”或“<=”，因此额外的键不会破坏定位
			 * 方案。但是，从同样的道理来说，如果我们无法使用所有
			 * 行成员，那么我们所使用的行比较部分必须被视为仅仅是“>=”或“<=”
			 * 条件，因此我们最好相应地调整strat_total。
			 */
			if (fc_i == fc_keysCount - 1)
			{
				bool		fc_used_all_subkeys = false;

				Assert(!(fc_subkey->sk_flags & SK_ROW_END));
				for (;;)
				{
					fc_subkey++;
					Assert(fc_subkey->sk_flags & SK_ROW_MEMBER);
					if (fc_subkey->sk_attno != fc_keysCount + 1)
						break;	/* 超出顺序，无法使用 */
					if (fc_subkey->sk_strategy != fc_cur->sk_strategy)
						break;	/* 错误的方向，无法使用 */
					if (fc_subkey->sk_flags & SK_ISNULL)
						break;	/* 不能使用空键 */
					Assert(fc_keysCount < INDEX_MAX_KEYS);
					memcpy(fc_inskey.scankeys + fc_keysCount, fc_subkey,
						   sizeof(ScanKeyData));
					fc_keysCount++;
					if (fc_subkey->sk_flags & SK_ROW_END)
					{
						fc_used_all_subkeys = true;
						break;
					}
				}
				if (!fc_used_all_subkeys)
				{
					switch (fc_strat_total)
					{
						case BTLessStrategyNumber:
							fc_strat_total = BTLessEqualStrategyNumber;
							break;
						case BTGreaterStrategyNumber:
							fc_strat_total = BTGreaterEqualStrategyNumber;
							break;
					}
				}
				break;			/* 外部循环已完成 */
			}
		}
		else
		{
			/*
			 * 普通比较键。将搜索样式扫描键
			 * 转换为插入扫描键，通过用
			 * 适当的btree比较函数替换sk_func。
			 *
			 * 如果scankey操作符不是跨类型比较，我们可以使用
			 * 缓存的比较函数；否则必须在
			 * 目录中查找。 （这不会导致无限递归，因为没有
			 * 由syscache查找启动的索引扫描会使用跨数据类型
			 * 操作符。）
			 *
			 * 我们支持约定sk_subtype == InvalidOid意味着
			 * opclass输入类型；这是一个简化
			 * ScanKeyInit()的黑客。
			 */
			if (fc_cur->sk_subtype == fc_rel->rd_opcintype[fc_i] ||
				fc_cur->sk_subtype == InvalidOid)
			{
				FmgrInfo   *fc_procinfo;

				fc_procinfo = index_getprocinfo(fc_rel, fc_cur->sk_attno, BTORDER_PROC);
				ScanKeyEntryInitializeWithInfo(fc_inskey.scankeys + fc_i,
											   fc_cur->sk_flags,
											   fc_cur->sk_attno,
											   InvalidStrategy,
											   fc_cur->sk_subtype,
											   fc_cur->sk_collation,
											   fc_procinfo,
											   fc_cur->sk_argument);
			}
			else
			{
				RegProcedure fc_cmp_proc;

				fc_cmp_proc = get_opfamily_proc(fc_rel->rd_opfamily[fc_i],
											 fc_rel->rd_opcintype[fc_i],
											 fc_cur->sk_subtype,
											 BTORDER_PROC);
				if (!RegProcedureIsValid(fc_cmp_proc))
					elog(ERROR, "missing support function %d(%u,%u) for attribute %d of index \"%s\"",
						 BTORDER_PROC, fc_rel->rd_opcintype[fc_i], fc_cur->sk_subtype,
						 fc_cur->sk_attno, RelationGetRelationName(fc_rel));
				ScanKeyEntryInitialize(fc_inskey.scankeys + fc_i,
									   fc_cur->sk_flags,
									   fc_cur->sk_attno,
									   InvalidStrategy,
									   fc_cur->sk_subtype,
									   fc_cur->sk_collation,
									   fc_cmp_proc,
									   fc_cur->sk_argument);
			}
		}
	}

	/*----------
	 * 检查选择的初始定位策略，以确定我们需要从何处开始扫描，并设置标志变量以控制
	 * 下面的代码。
	 *
	 * 如果nextkey = false，_bt_search和_bt_binsrch将定位第一个
	 * >=扫描键的项。如果nextkey = true，它们将定位第一个
	 * >扫描键的项。
	 *
	 * 如果goback = true，我们将回退一个项，而如果
	 * goback = false，我们将从定位的项开始扫描。
	 *----------
	 */
	switch (fc_strat_total)
	{
		case BTLessStrategyNumber:

			/*
			 * 寻找第一个>=scankey的项，然后向后退一步，达到最后一个
			 * <scankey的项。 （注意：此定位策略仅用于
			 * 向后扫描，因此这始终是正确的起始位置。）
			 */
			fc_nextkey = false;
			fc_goback = true;
			break;

		case BTLessEqualStrategyNumber:

			/*
			 * 寻找第一个>scankey的项，然后向后退一步，达到最后一个
			 * <=scankey的项。 （注意：此定位策略仅用于
			 * 向后扫描，因此这始终是正确的起始位置。）
			 */
			fc_nextkey = true;
			fc_goback = true;
			break;

		case BTEqualStrategyNumber:

			/*
			 * 如果指定了向后扫描，需以最后一个相等的
			 * 项开始，而不是第一个。
			 */
			if (ScanDirectionIsBackward(fc_dir))
			{
				/*
				 * 这与<=策略相同。我们将在
				 * 结束时检查找到的项是否实际为=。
				 */
				fc_nextkey = true;
				fc_goback = true;
			}
			else
			{
				/*
				 * 这与>=策略相同。我们将在
				 * 结束时检查找到的项是否实际为=。
				 */
				fc_nextkey = false;
				fc_goback = false;
			}
			break;

		case BTGreaterEqualStrategyNumber:

			/*
			 * 寻找第一个>=scankey的项。 （这仅用于向前
			 * 扫描。）
			 */
			fc_nextkey = false;
			fc_goback = false;
			break;

		case BTGreaterStrategyNumber:

			/*
			 * 寻找第一个>scankey的项。 （这仅用于向前
			 * 扫描。）
			 */
			fc_nextkey = true;
			fc_goback = false;
			break;

		default:
			/* 不能到这里，但保持编译器安静 */
			elog(ERROR, "unrecognized strat_total: %d", (int) fc_strat_total);
			return false;
	}

	/* 初始化剩余的插入扫描键字段 */
	_bt_metaversion(fc_rel, &fc_inskey.heapkeyspace, &fc_inskey.allequalimage);
	fc_inskey.anynullkeys = false; /* 未使用 */
	fc_inskey.nextkey = fc_nextkey;
	fc_inskey.pivotsearch = false;
	fc_inskey.scantid = NULL;
	fc_inskey.keysz = fc_keysCount;

	/*
	 * 使用制造的插入扫描键下降树并
	 * 定位到目标叶子页面。
	 */
	fc_stack = _bt_search(fc_rel, &fc_inskey, &fc_buf, BT_READ, fc_scan->xs_snapshot);

	/* 不需要保留堆栈... */
	_bt_freestack(fc_stack);

	if (!BufferIsValid(fc_buf))
	{
		/*
		 * 我们只有在索引完全为空时才能到这里。锁定关系
		 * 因为没有更细粒度的锁定可用。没有缓冲区锁，可能
		 * 另一个事务会在 _bt_search() 和 PredicateLockRelation() 之间插入数据。
		 * 我们必须在获取关系级别的谓词锁后再尝试一次，以缩小一个狭窄
		 * 的窗口，在这个窗口内我们不会扫描并发插入的元组，但写入者不会看到我们的谓词锁。
		 */
		if (IsolationIsSerializable())
		{
			PredicateLockRelation(fc_rel, fc_scan->xs_snapshot);
			fc_stack = _bt_search(fc_rel, &fc_inskey, &fc_buf, BT_READ,
							   fc_scan->xs_snapshot);
			_bt_freestack(fc_stack);
		}

		if (!BufferIsValid(fc_buf))
		{
			/*
			 * 将并行扫描标记为完成，以便所有工作程序可以完成
			 * 他们的扫描。
			 */
			_bt_parallel_done(fc_scan);
			BTScanPosInvalidate(fc_so->currPos);
			return false;
		}
	}

	PredicateLockPage(fc_rel, BufferGetBlockNumber(fc_buf), fc_scan->xs_snapshot);

	fc__bt_initialize_more_data(fc_so, fc_dir);

	/* 定位到页面上的准确项 */
	fc_offnum = fc__bt_binsrch(fc_rel, &fc_inskey, fc_buf);

	/*
	 * 如果 nextkey = false，我们位于第一个 ≥ 扫描键的项，
	 * 或可能位于一个页面的末尾，其中所有现有项都小于
	 * 扫描键，并且我们知道后续页面上的所有内容都大于
	 * 或等于扫描键。
	 *
	 * 如果 nextkey = true，我们位于第一个 > 扫描键的项，
	 * 或可能位于一个页面的末尾，其中所有现有项都小于
	 * 或等于扫描键，并且我们知道后续页面上的所有内容都大于扫描键。
	 *
	 * 实际所需的起始点要么是这个项，要么是前一个项，或者在页面末尾的情况下，是下一页的第一个
	 * 项或这一页的最后一个项。如果需要，调整起始偏移量。
	 * （如果这导致偏移量在第一个项之前或在最后一个项之后，
	 * _bt_readpage 将报告未找到项，然后我们会在需要时转到
	 * 下一页。）
	 */
	if (fc_goback)
		fc_offnum = OffsetNumberPrev(fc_offnum);

	/* 记住我们锁定了哪个缓冲区（如果有的话） */
	Assert(!BTScanPosIsValid(fc_so->currPos));
	fc_so->currPos.buf = fc_buf;

	/*
	 * 现在从扫描的第一页加载数据。
	 */
	if (!fc__bt_readpage(fc_scan, fc_dir, fc_offnum))
	{
		/*
		 * 这一页上没有实际匹配的数据。尝试前进到
		 * 下一页。如果根本没有匹配的数据，则返回 false。
		 */
		_bt_unlockbuf(fc_scan->indexRelation, fc_so->currPos.buf);
		if (!fc__bt_steppage(fc_scan, fc_dir))
			return false;
	}
	else
	{
		/* 释放当前页面的锁定，可能还有引脚 */
		fc__bt_drop_lock_and_maybe_pin(fc_scan, &fc_so->currPos);
	}

readcomplete:
	/* 好的，itemIndex 表示要返回的内容 */
	fc_currItem = &fc_so->currPos.items[fc_so->currPos.itemIndex];
	fc_scan->xs_heaptid = fc_currItem->heapTid;
	if (fc_scan->xs_want_itup)
		fc_scan->xs_itup = (IndexTuple) (fc_so->currTuples + fc_currItem->tupleOffset);

	return true;
}

/*
 *	_bt_next() -- 获取扫描中的下一个项。
 *
 *		进入时，so->currPos 描述当前页面，可能已被固定
 *		但未被锁定，so->currPos.itemIndex 标识之前返回的项。
 *
 *		成功退出时，scan->xs_ctup.t_self 被设置为
 *		下一个堆元组的 TID，如果请求，scan->xs_itup 指向一个副本
 *		索引元组。so->currPos 根据需要更新。
 *
 *		在失败退出（没有更多元组）时，我们释放引脚并设置
 *		so->currPos.buf 为 InvalidBuffer。
 */
bool _bt_next(IndexScanDesc fc_scan, ScanDirection fc_dir)
{
	BTScanOpaque fc_so = (BTScanOpaque) fc_scan->opaque;
	BTScanPosItem *fc_currItem;

	/*
	 * 在当前页面上向下一个元组推进；或者如果没有更多，尝试
	 * 步进到下一页的数据。
	 */
	if (ScanDirectionIsForward(fc_dir))
	{
		if (++fc_so->currPos.itemIndex > fc_so->currPos.lastItem)
		{
			if (!fc__bt_steppage(fc_scan, fc_dir))
				return false;
		}
	}
	else
	{
		if (--fc_so->currPos.itemIndex < fc_so->currPos.firstItem)
		{
			if (!fc__bt_steppage(fc_scan, fc_dir))
				return false;
		}
	}

	/* 好的，itemIndex 表示要返回的内容 */
	fc_currItem = &fc_so->currPos.items[fc_so->currPos.itemIndex];
	fc_scan->xs_heaptid = fc_currItem->heapTid;
	if (fc_scan->xs_want_itup)
		fc_scan->xs_itup = (IndexTuple) (fc_so->currTuples + fc_currItem->tupleOffset);

	return true;
}

/*
 *	_bt_readpage() -- 将当前索引页面的数据加载到 so->currPos
 *
 * 调用者必须已经固定并读锁了 so->currPos.buf；这里 buffer 的状态
 * 不会改变。此外，currPos.moreLeft 和 moreRight 必须有效；
 * 它们会根据需要进行更新。so->currPos 的所有其他字段在这里
 * 被重新初始化。
 *
 * 我们从 offnum 开始扫描当前页面，并在指示的
 * 方向上移动。所有符合扫描条件的项被加载到 currPos.items 中。
 * 如果 _bt_checkkeys 报告在当前扫描方向上没有更多符合的元组，
 * 则 moreLeft 或 moreRight（根据需要）会被清除。
 *
 * 在并行扫描的情况下，调用者必须在调用此函数之前调用 _bt_parallel_seize；
 * 这个函数在返回之前会调用 _bt_parallel_release。
 *
 * 如果在页面上找到了任何匹配项，则返回 true；如果没有则返回 false。
 */
static bool fc__bt_readpage(IndexScanDesc fc_scan, ScanDirection fc_dir, OffsetNumber fc_offnum)
{
	BTScanOpaque fc_so = (BTScanOpaque) fc_scan->opaque;
	Page		fc_page;
	BTPageOpaque fc_opaque;
	OffsetNumber fc_minoff;
	OffsetNumber fc_maxoff;
	int			fc_itemIndex;
	bool		fc_continuescan;
	int			fc_indnatts;

	/*
	 * 我们必须固定和锁定 buffer，但这里不能使用
	 * 通常的宏；这个函数使其适用于 currPos。
	 */
	Assert(BufferIsValid(fc_so->currPos.buf));

	fc_page = BufferGetPage(fc_so->currPos.buf);
	fc_opaque = BTPageGetOpaque(fc_page);

	/* 允许下一个页面由并行工作者处理 */
	if (fc_scan->parallel_scan)
	{
		if (ScanDirectionIsForward(fc_dir))
			_bt_parallel_release(fc_scan, fc_opaque->btpo_next);
		else
			_bt_parallel_release(fc_scan, BufferGetBlockNumber(fc_so->currPos.buf));
	}

	fc_continuescan = true;		/* 默认假设 */
	fc_indnatts = IndexRelationGetNumberOfAttributes(fc_scan->indexRelation);
	fc_minoff = P_FIRSTDATAKEY(fc_opaque);
	fc_maxoff = PageGetMaxOffsetNumber(fc_page);

	/*
	 * 我们记录 buffer 的块号，以便稍后能够释放固定。
	 * 这允许我们在需要时重新读取 buffer 以获取提示。
	 */
	fc_so->currPos.currPage = BufferGetBlockNumber(fc_so->currPos.buf);

	/*
	 * 我们在读取页面时保存该页面的 LSN，以便知道是否
	 * 在稍后将 LP_DEAD 提示应用于该页面是安全的。这允许我们
	 * 对于 MVCC 扫描释放固定，从而允许清理避免阻塞。
	 */
	fc_so->currPos.lsn = BufferGetLSNAtomic(fc_so->currPos.buf);

	/*
	 * 我们在扫描时必须保存页面的右链接；这告诉我们
	 * 完成这些项后该向右移动到哪里。左链接没有相应的需求，
	 * 因为拆分总是向右进行。
	 */
	fc_so->currPos.nextPage = fc_opaque->btpo_next;

	/* 将元组工作区初始化为空 */
	fc_so->currPos.nextTupleOffset = 0;

	/*
	 * 现在当前页面已被一致化，宏应该是
	 * 可用的。
	 */
	Assert(BTScanPosIsPinned(fc_so->currPos));

	if (ScanDirectionIsForward(fc_dir))
	{
		/* 以升序加载 items[] */
		fc_itemIndex = 0;

		fc_offnum = Max(fc_offnum, fc_minoff);

		while (fc_offnum <= fc_maxoff)
		{
			ItemId		fc_iid = PageGetItemId(fc_page, fc_offnum);
			IndexTuple	fc_itup;

			/*
			 * 如果扫描指定不返回被杀元组，则我们
			 * 将被杀元组视为未通过条件
			 */
			if (fc_scan->ignore_killed_tuples && ItemIdIsDead(fc_iid))
			{
				fc_offnum = OffsetNumberNext(fc_offnum);
				continue;
			}

			fc_itup = (IndexTuple) PageGetItem(fc_page, fc_iid);

			if (_bt_checkkeys(fc_scan, fc_itup, fc_indnatts, fc_dir, &fc_continuescan))
			{
				/* 元组通过所有扫描键条件 */
				if (!BTreeTupleIsPosting(fc_itup))
				{
					/* 记住它 */
					fc__bt_saveitem(fc_so, fc_itemIndex, fc_offnum, fc_itup);
					fc_itemIndex++;
				}
				else
				{
					int			fc_tupleOffset;

					/*
					 * 设置状态以返回发布列表，并记住第一个
					 * TID
					 */
					fc_tupleOffset =
						fc__bt_setuppostingitems(fc_so, fc_itemIndex, fc_offnum,
											  BTreeTupleGetPostingN(fc_itup, 0),
											  fc_itup);
					fc_itemIndex++;
					/* 记住额外的 TIDs */
					for (int fc_i = 1; fc_i < BTreeTupleGetNPosting(fc_itup); fc_i++)
					{
						fc__bt_savepostingitem(fc_so, fc_itemIndex, fc_offnum,
											BTreeTupleGetPostingN(fc_itup, fc_i),
											fc_tupleOffset);
						fc_itemIndex++;
					}
				}
			}
			/* 当 !continuescan 时，不能再有匹配项，因此停止 */
			if (!fc_continuescan)
				break;

			fc_offnum = OffsetNumberNext(fc_offnum);
		}

		/*
		 * 当高键指示不会在右侧找到更多匹配项时，
		 * 我们不需要访问右侧页面。
		 *
		 * 像这样检查高键的效果比你想象的更好。
		 * 叶页拆分在两个最不相似的元组之间选择一个拆分点（这是基于
		 * 需要均匀共享空闲空间而加权的）。具有只能出现在右侧
		 * 兄弟页面的非枢轴元组上的高键属性值的叶页面是
		 * 常见的。
		 */
		if (fc_continuescan && !P_RIGHTMOST(fc_opaque))
		{
			ItemId		fc_iid = PageGetItemId(fc_page, P_HIKEY);
			IndexTuple	fc_itup = (IndexTuple) PageGetItem(fc_page, fc_iid);
			int			fc_truncatt;

			fc_truncatt = BTreeTupleGetNAtts(fc_itup, fc_scan->indexRelation);
			_bt_checkkeys(fc_scan, fc_itup, fc_truncatt, fc_dir, &fc_continuescan);
		}

		if (!fc_continuescan)
			fc_so->currPos.moreRight = false;

		Assert(fc_itemIndex <= MaxTIDsPerBTreePage);
		fc_so->currPos.firstItem = 0;
		fc_so->currPos.lastItem = fc_itemIndex - 1;
		fc_so->currPos.itemIndex = 0;
	}
	else
	{
		/* 以降序加载 items[] */
		fc_itemIndex = MaxTIDsPerBTreePage;

		fc_offnum = Min(fc_offnum, fc_maxoff);

		while (fc_offnum >= fc_minoff)
		{
			ItemId		fc_iid = PageGetItemId(fc_page, fc_offnum);
			IndexTuple	fc_itup;
			bool		fc_tuple_alive;
			bool		fc_passes_quals;

			/*
			 * 如果扫描指定不返回已删除的元组，则我们
			 * 将已删除的元组视为未通过条件。大多数情况下，
			 * 不检查元组的索引键是有利的，而是跳到下一个元组（实际上是前一个，
			 * 因为我们正在向后扫描）。然而，如果这是页面上的第一个
			 * 元组，我们会检查索引键，以防无用地向左推进页面。这类似于
			 * 正向扫描中使用的高键优化。
			 */
			if (fc_scan->ignore_killed_tuples && ItemIdIsDead(fc_iid))
			{
				Assert(fc_offnum >= P_FIRSTDATAKEY(fc_opaque));
				if (fc_offnum > P_FIRSTDATAKEY(fc_opaque))
				{
					fc_offnum = OffsetNumberPrev(fc_offnum);
					continue;
				}

				fc_tuple_alive = false;
			}
			else
				fc_tuple_alive = true;

			fc_itup = (IndexTuple) PageGetItem(fc_page, fc_iid);

			fc_passes_quals = _bt_checkkeys(fc_scan, fc_itup, fc_indnatts, fc_dir,
										 &fc_continuescan);
			if (fc_passes_quals && fc_tuple_alive)
			{
				/* 元组通过所有扫描键条件 */
				if (!BTreeTupleIsPosting(fc_itup))
				{
					/* 记住它 */
					fc_itemIndex--;
					fc__bt_saveitem(fc_so, fc_itemIndex, fc_offnum, fc_itup);
				}
				else
				{
					int			fc_tupleOffset;

					/*
					 * 设置状态以返回发布列表，并记住第一个
					 * TID。
					 *
					 * 请注意，我们故意以升序堆 TID
					 * 顺序保存/返回来自发布列表的项以进行向后
					 * 扫描。这允许 _bt_killitems() 对与
					 * 相同发布列表元组相关联的项的顺序做出
					 * 一致假设。
					 */
					fc_itemIndex--;
					fc_tupleOffset =
						fc__bt_setuppostingitems(fc_so, fc_itemIndex, fc_offnum,
											  BTreeTupleGetPostingN(fc_itup, 0),
											  fc_itup);
					/* 记住额外的 TIDs */
					for (int fc_i = 1; fc_i < BTreeTupleGetNPosting(fc_itup); fc_i++)
					{
						fc_itemIndex--;
						fc__bt_savepostingitem(fc_so, fc_itemIndex, fc_offnum,
											BTreeTupleGetPostingN(fc_itup, fc_i),
											fc_tupleOffset);
					}
				}
			}
			if (!fc_continuescan)
			{
				/* 不能再有更多匹配项，因此停止 */
				fc_so->currPos.moreLeft = false;
				break;
			}

			fc_offnum = OffsetNumberPrev(fc_offnum);
		}

		Assert(fc_itemIndex >= 0);
		fc_so->currPos.firstItem = fc_itemIndex;
		fc_so->currPos.lastItem = MaxTIDsPerBTreePage - 1;
		fc_so->currPos.itemIndex = MaxTIDsPerBTreePage - 1;
	}

	return (fc_so->currPos.firstItem <= fc_so->currPos.lastItem);
}

/* 将索引项保存到 so->currPos.items[itemIndex] */
static void fc__bt_saveitem(BTScanOpaque fc_so, int fc_itemIndex,
			 OffsetNumber fc_offnum, IndexTuple fc_itup)
{
	BTScanPosItem *fc_currItem = &fc_so->currPos.items[fc_itemIndex];

	Assert(!BTreeTupleIsPivot(fc_itup) && !BTreeTupleIsPosting(fc_itup));

	fc_currItem->heapTid = fc_itup->t_tid;
	fc_currItem->indexOffset = fc_offnum;
	if (fc_so->currTuples)
	{
		Size		fc_itupsz = IndexTupleSize(fc_itup);

		fc_currItem->tupleOffset = fc_so->currPos.nextTupleOffset;
		memcpy(fc_so->currTuples + fc_so->currPos.nextTupleOffset, fc_itup, fc_itupsz);
		fc_so->currPos.nextTupleOffset += MAXALIGN(fc_itupsz);
	}
}

/*
 * 设置状态以从单个发布列表元组中保存 TIDs/项。
 *
 * 将索引项保存到 so->currPos.items[itemIndex] 以获取
 * 首先返回的 TID。对于发布列表的第二个或后续 TID，
 * 应通过调用 _bt_savepostingitem() 来保存。
 *
 * 如果需要，返回主元组存储空间中的偏移量。
 */
static int fc__bt_setuppostingitems(BTScanOpaque fc_so, int fc_itemIndex, OffsetNumber fc_offnum,
					  ItemPointer fc_heapTid, IndexTuple fc_itup)
{
	BTScanPosItem *fc_currItem = &fc_so->currPos.items[fc_itemIndex];

	Assert(BTreeTupleIsPosting(fc_itup));

	fc_currItem->heapTid = *fc_heapTid;
	fc_currItem->indexOffset = fc_offnum;
	if (fc_so->currTuples)
	{
		/* 保存基础的 IndexTuple（截断发布列表） */
		IndexTuple	fc_base;
		Size		fc_itupsz = BTreeTupleGetPostingOffset(fc_itup);

		fc_itupsz = MAXALIGN(fc_itupsz);
		fc_currItem->tupleOffset = fc_so->currPos.nextTupleOffset;
		fc_base = (IndexTuple) (fc_so->currTuples + fc_so->currPos.nextTupleOffset);
		memcpy(fc_base, fc_itup, fc_itupsz);
		/* 防御性地减少工作区索引元组头大小 */
		fc_base->t_info &= ~INDEX_SIZE_MASK;
		fc_base->t_info |= fc_itupsz;
		fc_so->currPos.nextTupleOffset += fc_itupsz;

		return fc_currItem->tupleOffset;
	}

	return 0;
}

/*
 * 将索引项保存到 so->currPos.items[itemIndex] 以获取当前发布
 * 元组。
 *
 * 假设已为当前发布列表元组调用 _bt_setuppostingitems()。
 * 调用者将其返回值作为 tupleOffset 传递。
 */
static inline void fc__bt_savepostingitem(BTScanOpaque fc_so, int fc_itemIndex, OffsetNumber fc_offnum,
					ItemPointer fc_heapTid, int fc_tupleOffset)
{
	BTScanPosItem *fc_currItem = &fc_so->currPos.items[fc_itemIndex];

	fc_currItem->heapTid = *fc_heapTid;
	fc_currItem->indexOffset = fc_offnum;

	/*
	 * 让仅索引扫描为来自同一发布列表的每个 TID 返回
	 * 相同的基础 IndexTuple
	 */
	if (fc_so->currTuples)
		fc_currItem->tupleOffset = fc_tupleOffset;
}

/*
 *	_bt_steppage() -- 步进到下一个包含有效数据的页面
 *
 * 进入时，如果 so->currPos.buf 有效，则缓冲区被固定但未锁定；
 * 如果固定，我们将在移动到下一个页面之前释放固定。进入时
 * 缓冲区没有被锁定。
 *
 * 对于使用非 MVCC 快照的扫描成功，我们在该页面上保持一个
 * 固定，但不进行读取锁定。如果我们没有保持固定，
 * 将 so->currPos.buf 设置为 InvalidBuffer。我们返回 true 以表示成功。
 */
static bool fc__bt_steppage(IndexScanDesc fc_scan, ScanDirection fc_dir)
{
	BTScanOpaque fc_so = (BTScanOpaque) fc_scan->opaque;
	BlockNumber fc_blkno = InvalidBlockNumber;
	bool		fc_status;

	Assert(BTScanPosIsValid(fc_so->currPos));

	/* 在离开当前页面之前，处理任何已删除的项 */
	if (fc_so->numKilled > 0)
		_bt_killitems(fc_scan);

	/*
	 * 在我们修改 currPos 之前，如果有需要的标记位置，
	 * 复制页面数据。
	 */
	if (fc_so->markItemIndex >= 0)
	{
		/* 在当前缓冲区上增加固定以分配给标记缓冲区 */
		if (BTScanPosIsPinned(fc_so->currPos))
			IncrBufferRefCount(fc_so->currPos.buf);
		memcpy(&fc_so->markPos, &fc_so->currPos,
			   offsetof(BTScanPosData, items[1]) +
			   fc_so->currPos.lastItem * sizeof(BTScanPosItem));
		if (fc_so->markTuples)
			memcpy(fc_so->markTuples, fc_so->currTuples,
				   fc_so->currPos.nextTupleOffset);
		fc_so->markPos.itemIndex = fc_so->markItemIndex;
		fc_so->markItemIndex = -1;
	}

	if (ScanDirectionIsForward(fc_dir))
	{
		/* 向右移动到下一页数据 */
		if (fc_scan->parallel_scan != NULL)
		{
			/*
			 * 抓住扫描以获取下一个块号；如果扫描已经结束，
			 * 则退出。
			 */
			fc_status = _bt_parallel_seize(fc_scan, &fc_blkno);
			if (!fc_status)
			{
				/* 释放先前的缓冲区，如果已固定 */
				BTScanPosUnpinIfPinned(fc_so->currPos);
				BTScanPosInvalidate(fc_so->currPos);
				return false;
			}
		}
		else
		{
			/* 不是并行的，因此使用之前保存的 nextPage 链接。 */
			fc_blkno = fc_so->currPos.nextPage;
		}

		/* 记住我们留下了一页带数据的页面 */
		fc_so->currPos.moreLeft = true;

		/* 释放先前的缓冲区，如果已固定 */
		BTScanPosUnpinIfPinned(fc_so->currPos);
	}
	else
	{
		/* 记住我们留下了一页带数据的页面 */
		fc_so->currPos.moreRight = true;

		if (fc_scan->parallel_scan != NULL)
		{
			/*
			 * 抓取扫描以获取当前块号；如果扫描已经结束，退出。
			 */
			fc_status = _bt_parallel_seize(fc_scan, &fc_blkno);
			BTScanPosUnpinIfPinned(fc_so->currPos);
			if (!fc_status)
			{
				BTScanPosInvalidate(fc_so->currPos);
				return false;
			}
		}
		else
		{
			/* 不是并行的，所以只需使用我们自己对当前页面的理解 */
			fc_blkno = fc_so->currPos.currPage;
		}
	}

	if (!fc__bt_readnextpage(fc_scan, fc_blkno, fc_dir))
		return false;

	/* 释放当前页面的锁定，可能还有引脚 */
	fc__bt_drop_lock_and_maybe_pin(fc_scan, &fc_so->currPos);

	return true;
}

/*
 *	_bt_readnextpage() -- 读取包含扫描有效数据的下一页
 *
 * 成功退出时，so->currPos 更新为包含下一页有趣数据。调用者负责在成功后释放缓冲区上的锁和锁定。返回 true 表示成功。
 *
 * 如果给定方向没有更多匹配记录，则我们释放所有锁和锁定，将 so->currPos.buf 设置为 InvalidBuffer，并返回 false。
 */
static bool fc__bt_readnextpage(IndexScanDesc fc_scan, BlockNumber fc_blkno, ScanDirection fc_dir)
{
	BTScanOpaque fc_so = (BTScanOpaque) fc_scan->opaque;
	Relation	fc_rel;
	Page		fc_page;
	BTPageOpaque fc_opaque;
	bool		fc_status;

	fc_rel = fc_scan->indexRelation;

	if (ScanDirectionIsForward(fc_dir))
	{
		for (;;)
		{
			/*
			 * 如果我们在扫描的末尾，放弃并标记并行扫描为
			 * 完成，以便所有工作线程可以结束它们的扫描
			 */
			if (fc_blkno == P_NONE || !fc_so->currPos.moreRight)
			{
				_bt_parallel_done(fc_scan);
				BTScanPosInvalidate(fc_so->currPos);
				return false;
			}
			/* 在我们没有持有任何缓冲区锁时检查中断 */
			CHECK_FOR_INTERRUPTS();
			/* 向右移动一页 */
			fc_so->currPos.buf = _bt_getbuf(fc_rel, fc_blkno, BT_READ);
			fc_page = BufferGetPage(fc_so->currPos.buf);
			TestForOldSnapshot(fc_scan->xs_snapshot, fc_rel, fc_page);
			fc_opaque = BTPageGetOpaque(fc_page);
			/* 检查删除的页面 */
			if (!P_IGNORE(fc_opaque))
			{
				PredicateLockPage(fc_rel, fc_blkno, fc_scan->xs_snapshot);
				/* 查看此页面上是否有任何匹配项 */
				/* 注意，如果我们可以停止，这将清除 moreRight */
				if (fc__bt_readpage(fc_scan, fc_dir, P_FIRSTDATAKEY(fc_opaque)))
					break;
			}
			else if (fc_scan->parallel_scan != NULL)
			{
				/* 允许下一个页面由并行工作者处理 */
				_bt_parallel_release(fc_scan, fc_opaque->btpo_next);
			}

			/* 不，继续前进 */
			if (fc_scan->parallel_scan != NULL)
			{
				_bt_relbuf(fc_rel, fc_so->currPos.buf);
				fc_status = _bt_parallel_seize(fc_scan, &fc_blkno);
				if (!fc_status)
				{
					BTScanPosInvalidate(fc_so->currPos);
					return false;
				}
			}
			else
			{
				fc_blkno = fc_opaque->btpo_next;
				_bt_relbuf(fc_rel, fc_so->currPos.buf);
			}
		}
	}
	else
	{
		/*
		 * 这应该只在并行情况下发生，当其他后端
		 * 推进了扫描。
		 */
		if (fc_so->currPos.currPage != fc_blkno)
		{
			BTScanPosUnpinIfPinned(fc_so->currPos);
			fc_so->currPos.currPage = fc_blkno;
		}

		/*
		 * 向左移动到下一页数据。由于可能性较大，
		 * 此过程比向右移动要复杂得多，因为页面
		 * 在我们前往它的过程中可能会拆分，加上
		 * 我们离开它后可能会删除我们所处的页面。有关详细信息，请参阅 nbtree/README。
		 *
		 * 可能可以重组此代码，以减少
		 * 锁定和锁定的开销，但这需要在初始读取时捕获左指针，并在这里使用它，
		 * 以及对 _bt_walk_left() 和下面的代码进行重大更改。不清楚这是否会有利，
		 * 因为如果立即左侧的页面在我们读取此页面后和在我们左移之前拆分，
		 * 我们将需要访问的页面比当前代码多。
		 *
		 * 注意，如果我们改变代码以便在非 MVCC 快照
		 * 的扫描中释放锁定，我们将需要修改左移的代码，
		 * 以考虑引用页面已被删除的可能性。只要缓冲区处于锁定状态或快照
		 * 是 MVCC，该页面就不能超越半死状态变为完全
		 * 删除。
		 */
		if (BTScanPosIsPinned(fc_so->currPos))
			_bt_lockbuf(fc_rel, fc_so->currPos.buf, BT_READ);
		else
			fc_so->currPos.buf = _bt_getbuf(fc_rel, fc_so->currPos.currPage, BT_READ);

		for (;;)
		{
			/* 如果我们知道左侧没有匹配键，就完成了 */
			if (!fc_so->currPos.moreLeft)
			{
				_bt_relbuf(fc_rel, fc_so->currPos.buf);
				_bt_parallel_done(fc_scan);
				BTScanPosInvalidate(fc_so->currPos);
				return false;
			}

			/* 步进到下一个物理页面 */
			fc_so->currPos.buf = fc__bt_walk_left(fc_rel, fc_so->currPos.buf,
											fc_scan->xs_snapshot);

			/* 如果我们在物理上到达索引末尾，返回失败 */
			if (fc_so->currPos.buf == InvalidBuffer)
			{
				_bt_parallel_done(fc_scan);
				BTScanPosInvalidate(fc_so->currPos);
				return false;
			}

			/*
			 * 好吧，我们成功地向左移动到一个未删除的页面。如果
			 * 它不是半死状态并且包含匹配元组，则完成。否则，循环回去
			 * 再做一次。
			 */
			fc_page = BufferGetPage(fc_so->currPos.buf);
			TestForOldSnapshot(fc_scan->xs_snapshot, fc_rel, fc_page);
			fc_opaque = BTPageGetOpaque(fc_page);
			if (!P_IGNORE(fc_opaque))
			{
				PredicateLockPage(fc_rel, BufferGetBlockNumber(fc_so->currPos.buf), fc_scan->xs_snapshot);
				/* 查看此页面上是否有任何匹配项 */
				/* 注意，这将清除 moreLeft 如果我们可以停止 */
				if (fc__bt_readpage(fc_scan, fc_dir, PageGetMaxOffsetNumber(fc_page)))
					break;
			}
			else if (fc_scan->parallel_scan != NULL)
			{
				/* 允许下一个页面由并行工作者处理 */
				_bt_parallel_release(fc_scan, BufferGetBlockNumber(fc_so->currPos.buf));
			}

			/*
			 * 对于并行扫描，获取最后一个扫描的页面，因为在我们尝试获取扫描时，
			 * 其他工作者可能已经将扫描推进到不同的页面。我们必须基于
			 * 任何工作者最新扫描的页面继续。
			 */
			if (fc_scan->parallel_scan != NULL)
			{
				_bt_relbuf(fc_rel, fc_so->currPos.buf);
				fc_status = _bt_parallel_seize(fc_scan, &fc_blkno);
				if (!fc_status)
				{
					BTScanPosInvalidate(fc_so->currPos);
					return false;
				}
				fc_so->currPos.buf = _bt_getbuf(fc_rel, fc_blkno, BT_READ);
			}
		}
	}

	return true;
}

/*
 *	_bt_parallel_readpage() -- 读取当前页面，包含扫描的有效数据
 *
 * 在成功时，释放锁定，并可能在缓冲区上加锁。我们返回 true 
 * 表示成功。
 */
static bool fc__bt_parallel_readpage(IndexScanDesc fc_scan, BlockNumber fc_blkno, ScanDirection fc_dir)
{
	BTScanOpaque fc_so = (BTScanOpaque) fc_scan->opaque;

	fc__bt_initialize_more_data(fc_so, fc_dir);

	if (!fc__bt_readnextpage(fc_scan, fc_blkno, fc_dir))
		return false;

	/* 释放当前页面的锁定，可能还有引脚 */
	fc__bt_drop_lock_and_maybe_pin(fc_scan, &fc_so->currPos);

	return true;
}

/*
 * _bt_walk_left() -- 如果可能，向左移动一页
 *
 * 给定的缓冲区必须被锁定并读取锁定。这个锁定将在向左移动前解除。
 * 返回时，我们对返回的页面拥有锁定和读取锁定。
 *
 * 如果左侧没有页面，则返回 InvalidBuffer（在这种情况下不持有锁）。
 *
 * 在处理非叶子层级时，返回的页面可能是半死的；调用者应该检查该条件，
 * 如果重要，则再次向左移动。
 */
static Buffer fc__bt_walk_left(Relation fc_rel, Buffer fc_buf, Snapshot fc_snapshot)
{
	Page		fc_page;
	BTPageOpaque fc_opaque;

	fc_page = BufferGetPage(fc_buf);
	fc_opaque = BTPageGetOpaque(fc_page);

	for (;;)
	{
		BlockNumber fc_obknum;
		BlockNumber fc_lblkno;
		BlockNumber fc_blkno;
		int			fc_tries;

		/* 如果我们在树的末尾，释放缓冲区并返回失败 */
		if (P_LEFTMOST(fc_opaque))
		{
			_bt_relbuf(fc_rel, fc_buf);
			break;
		}
		/* 记住我们要向左移动的原始页面 */
		fc_obknum = BufferGetBlockNumber(fc_buf);
		/* 向左移动 */
		fc_blkno = fc_lblkno = fc_opaque->btpo_prev;
		_bt_relbuf(fc_rel, fc_buf);
		/* 在我们没有持有任何缓冲区锁时检查中断 */
		CHECK_FOR_INTERRUPTS();
		fc_buf = _bt_getbuf(fc_rel, fc_blkno, BT_READ);
		fc_page = BufferGetPage(fc_buf);
		TestForOldSnapshot(fc_snapshot, fc_rel, fc_page);
		fc_opaque = BTPageGetOpaque(fc_page);

		/*
		 * 如果这不是我们想要的页面，向右移动直到找到我们
		 * 想要的---但最多四次跳跃（一个任意限制）。如果到那时
		 * 我们仍未找到正确的页面，最可能的情况是
		 * 原始页面已经被删除，并且在兄弟链中根本不存在，
		 * 而不是其左侧兄弟已经分裂超过四次。
		 *
		 * 注意，在这里测试 P_ISDELETED 而不是 P_IGNORE 是正确的，
		 * 因为半死的页面仍在兄弟链中。调用者必须拒绝半死的页面（如果需要）。
		 */
		fc_tries = 0;
		for (;;)
		{
			if (!P_ISDELETED(fc_opaque) && fc_opaque->btpo_next == fc_obknum)
			{
				/* 找到所需页面，返回它 */
				return fc_buf;
			}
			if (P_RIGHTMOST(fc_opaque) || ++fc_tries > 4)
				break;
			fc_blkno = fc_opaque->btpo_next;
			fc_buf = _bt_relandgetbuf(fc_rel, fc_buf, fc_blkno, BT_READ);
			fc_page = BufferGetPage(fc_buf);
			TestForOldSnapshot(fc_snapshot, fc_rel, fc_page);
			fc_opaque = BTPageGetOpaque(fc_page);
		}

		/* 返回原始页面以查看情况如何 */
		fc_buf = _bt_relandgetbuf(fc_rel, fc_buf, fc_obknum, BT_READ);
		fc_page = BufferGetPage(fc_buf);
		TestForOldSnapshot(fc_snapshot, fc_rel, fc_page);
		fc_opaque = BTPageGetOpaque(fc_page);
		if (P_ISDELETED(fc_opaque))
		{
			/*
			 * 它已被删除。向右移动到第一个未删除的页面（一定存在一个）；
			 * 这是获得已删除页面的键空间的页面，因此从它向左移动将
			 * 带我们去我们想去的地方。
			 */
			for (;;)
			{
				if (P_RIGHTMOST(fc_opaque))
					elog(ERROR, "fell off the end of index \"%s\"",
						 RelationGetRelationName(fc_rel));
				fc_blkno = fc_opaque->btpo_next;
				fc_buf = _bt_relandgetbuf(fc_rel, fc_buf, fc_blkno, BT_READ);
				fc_page = BufferGetPage(fc_buf);
				TestForOldSnapshot(fc_snapshot, fc_rel, fc_page);
				fc_opaque = BTPageGetOpaque(fc_page);
				if (!P_ISDELETED(fc_opaque))
					break;
			}

			/*
			 * 现在返回到循环顶部，重置 obknum 指向这个
			 * 未删除页面，并再试一次。
			 */
		}
		else
		{
			/*
			 * 它没有被删除；解释最好是左侧页面被分裂或删除。
			 * 如果没有这个检查，如果出现任何问题我们将进入无限循环。
			 */
			if (fc_opaque->btpo_prev == fc_lblkno)
				elog(ERROR, "could not find left sibling of block %u in index \"%s\"",
					 fc_obknum, RelationGetRelationName(fc_rel));
			/* 可以用新的 lblkno 值再次尝试 */
		}
	}

	return InvalidBuffer;
}

/*
 * _bt_get_endpoint() -- 找到给定树层级的第一个或最后一个页面
 *
 * 如果索引为空，我们将返回 InvalidBuffer；任何其他失败
 * 条件将导致 ereport()。我们不会返回死页面。
 *
 * 返回的缓冲区已被锁定并读取锁定。
 */
Buffer _bt_get_endpoint(Relation fc_rel, uint32 fc_level, bool fc_rightmost,
				 Snapshot fc_snapshot)
{
	Buffer		fc_buf;
	Page		fc_page;
	BTPageOpaque fc_opaque;
	OffsetNumber fc_offnum;
	BlockNumber fc_blkno;
	IndexTuple	fc_itup;

	/*
	 * 如果我们要查找一个叶子页面，可以从快速根下降；
	 * 否则最好从真实根下降。 （在中间层次上没有必要更聪明。）
	 */
	if (fc_level == 0)
		fc_buf = _bt_getroot(fc_rel, BT_READ);
	else
		fc_buf = _bt_gettrueroot(fc_rel);

	if (!BufferIsValid(fc_buf))
		return InvalidBuffer;

	fc_page = BufferGetPage(fc_buf);
	TestForOldSnapshot(fc_snapshot, fc_rel, fc_page);
	fc_opaque = BTPageGetOpaque(fc_page);

	for (;;)
	{
		/*
		 * 如果我们落在一个已删除的页面上，右移以找到一个活动页面
		 * （必须有一个）。 此外，如果我们想要右侧的页面，如果需要，
		 * 向右移动以到达它（如果页面自从我们获得指针后分裂，
		 * 则可能会发生这种情况）。
		 */
		while (P_IGNORE(fc_opaque) ||
			   (fc_rightmost && !P_RIGHTMOST(fc_opaque)))
		{
			fc_blkno = fc_opaque->btpo_next;
			if (fc_blkno == P_NONE)
				elog(ERROR, "fell off the end of index \"%s\"",
					 RelationGetRelationName(fc_rel));
			fc_buf = _bt_relandgetbuf(fc_rel, fc_buf, fc_blkno, BT_READ);
			fc_page = BufferGetPage(fc_buf);
			TestForOldSnapshot(fc_snapshot, fc_rel, fc_page);
			fc_opaque = BTPageGetOpaque(fc_page);
		}

		/* 完成？ */
		if (fc_opaque->btpo_level == fc_level)
			break;
		if (fc_opaque->btpo_level < fc_level)
			ereport(ERROR,
					(errcode(ERRCODE_INDEX_CORRUPTED),
					 errmsg_internal("btree level %u not found in index \"%s\"",
									 fc_level, RelationGetRelationName(fc_rel))));

		/* 降到最左或最右的子页面 */
		if (fc_rightmost)
			fc_offnum = PageGetMaxOffsetNumber(fc_page);
		else
			fc_offnum = P_FIRSTDATAKEY(fc_opaque);

		fc_itup = (IndexTuple) PageGetItem(fc_page, PageGetItemId(fc_page, fc_offnum));
		fc_blkno = BTreeTupleGetDownLink(fc_itup);

		fc_buf = _bt_relandgetbuf(fc_rel, fc_buf, fc_blkno, BT_READ);
		fc_page = BufferGetPage(fc_buf);
		fc_opaque = BTPageGetOpaque(fc_page);
	}

	return fc_buf;
}

/*
 *	_bt_endpoint() -- 在索引中找到第一个或最后一个页面，并从那里扫描
 * 到满足所有条件的第一个关键字。
 *
 * 这是由 _bt_first() 使用的，以在我们确定扫描必须从索引的
 * 开始或结束处开始时设置扫描（分别用于向前或向后扫描）。退出
 * 条件与 _bt_first() 相同。
 */
static bool fc__bt_endpoint(IndexScanDesc fc_scan, ScanDirection fc_dir)
{
	Relation	fc_rel = fc_scan->indexRelation;
	BTScanOpaque fc_so = (BTScanOpaque) fc_scan->opaque;
	Buffer		fc_buf;
	Page		fc_page;
	BTPageOpaque fc_opaque;
	OffsetNumber fc_start;
	BTScanPosItem *fc_currItem;

	/*
	 * 向下扫描到最左或最右的叶子页面。这是 _bt_search() 的简化
	 * 版本。我们不维护栈，因为我们知道我们不会需要它。
	 */
	fc_buf = _bt_get_endpoint(fc_rel, 0, ScanDirectionIsBackward(fc_dir), fc_scan->xs_snapshot);

	if (!BufferIsValid(fc_buf))
	{
		/*
		 * 空索引。锁定整个关系，因为没有更细粒度的锁
		 * 存在。
		 */
		PredicateLockRelation(fc_rel, fc_scan->xs_snapshot);
		BTScanPosInvalidate(fc_so->currPos);
		return false;
	}

	PredicateLockPage(fc_rel, BufferGetBlockNumber(fc_buf), fc_scan->xs_snapshot);
	fc_page = BufferGetPage(fc_buf);
	fc_opaque = BTPageGetOpaque(fc_page);
	Assert(P_ISLEAF(fc_opaque));

	if (ScanDirectionIsForward(fc_dir))
	{
		/* 左侧可能有死页面，因此不是这样： */
		/* Assert(P_LEFTMOST(opaque)); */

		fc_start = P_FIRSTDATAKEY(fc_opaque);
	}
	else if (ScanDirectionIsBackward(fc_dir))
	{
		Assert(P_RIGHTMOST(fc_opaque));

		fc_start = PageGetMaxOffsetNumber(fc_page);
	}
	else
	{
		elog(ERROR, "invalid scan direction: %d", (int) fc_dir);
		fc_start = 0;				/* 保持编译器安静 */
	}

	/* 记住我们固定的缓冲区 */
	fc_so->currPos.buf = fc_buf;

	fc__bt_initialize_more_data(fc_so, fc_dir);

	/*
	 * 现在从扫描的第一页加载数据。
	 */
	if (!fc__bt_readpage(fc_scan, fc_dir, fc_start))
	{
		/*
		 * 这一页上没有实际匹配的数据。尝试前进到
		 * 下一页。如果根本没有匹配的数据，则返回 false。
		 */
		_bt_unlockbuf(fc_scan->indexRelation, fc_so->currPos.buf);
		if (!fc__bt_steppage(fc_scan, fc_dir))
			return false;
	}
	else
	{
		/* 释放当前页面的锁定，可能还有引脚 */
		fc__bt_drop_lock_and_maybe_pin(fc_scan, &fc_so->currPos);
	}

	/* 好的，itemIndex 表示要返回的内容 */
	fc_currItem = &fc_so->currPos.items[fc_so->currPos.itemIndex];
	fc_scan->xs_heaptid = fc_currItem->heapTid;
	if (fc_scan->xs_want_itup)
		fc_scan->xs_itup = (IndexTuple) (fc_so->currTuples + fc_currItem->tupleOffset);

	return true;
}

/*
 * _bt_initialize_more_data() -- 适当地初始化 moreLeft/moreRight
 * 以适应扫描方向
 */
static inline void fc__bt_initialize_more_data(BTScanOpaque fc_so, ScanDirection fc_dir)
{
	/* 适当地初始化 moreLeft/moreRight 以适应扫描方向 */
	if (ScanDirectionIsForward(fc_dir))
	{
		fc_so->currPos.moreLeft = false;
		fc_so->currPos.moreRight = true;
	}
	else
	{
		fc_so->currPos.moreLeft = true;
		fc_so->currPos.moreRight = false;
	}
	fc_so->numKilled = 0;			/* 只是 parano */
	fc_so->markItemIndex = -1;		/* 同上 */
}
